package demo8;


import sun.java2d.pipe.AAShapePipe;

import javax.lang.model.type.ArrayType;
import java.util.*;

public class Solution {
//
//    //1.火柴拼正方形(回溯剪枝)
//    public boolean makesquare(int[] matchsticks) {
//        int len = matchsticks.length;
//        if(len < 4) { //特判:正方形有四条边
//            return false;
//        }
//        //给所有火柴求和
//        int sum = 0;
//        for(int i = 0; i < matchsticks.length; i++) {
//            sum += matchsticks[i];
//        }
//        if(sum % 4 != 0) { //特判：正方形有四条边
//            return false;
//        }
//        //求出每一条边的长度
//        int lenSide = sum / 4;
//        //剪枝：降序排序更早触发回溯中的第一个continue
//        Arrays.sort(matchsticks);
//        //降序
//        for(int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
//            int tmp = matchsticks[i];
//            matchsticks[i] = matchsticks[j];
//            matchsticks[j] = tmp;
//        }
//        //四个桶
//        int[] bucket = new int[4];
//        return dfs(matchsticks, lenSide, bucket, 0);
//    }
//
//    private boolean dfs(int[] arr, int lenSide, int[] bucket, int index) {
//        if(index == arr.length) {
//            return true;
//        }
//        for(int i = 0; i < 4; i++) {
//            if(arr[index] + bucket[i] > lenSide) {//桶装不下了
//                continue;
//            }
//            bucket[i] += arr[index];
//            if(dfs(arr, lenSide, bucket, index + 1)) {
//                return true;
//            }
//            bucket[i] -= arr[index];
//        }
//        return false;
//    }
//
//    //1.火柴拼正方形(纯dfs)
//    private boolean flag;
//    public boolean makesquare(int[] matchsticks) {
//        int len = matchsticks.length;
//        if(len < 4) { //特判:正方形有四条边
//            return false;
//        }
//        //给所有火柴求和
//        int sum = 0;
//        for(int i = 0; i < matchsticks.length; i++) {
//            sum += matchsticks[i];
//        }
//        if(sum % 4 != 0) { //特判：正方形有四条边
//            return false;
//        }
//        //求出每一条边的长度
//        int lenSide = sum / 4;
//        //剪枝：降序排序更早触发回溯中的第一个continue
//        Arrays.sort(matchsticks);
//        //降序
//        for(int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
//            int tmp = matchsticks[i];
//            matchsticks[i] = matchsticks[j];
//            matchsticks[j] = tmp;
//        }
//        //四个桶
//        int[] bucket = new int[4];
//        dfs(matchsticks, lenSide, bucket, 0);
//        return flag;
//    }
//
//    private void dfs(int[] arr, int lenSide, int[] bucket, int index) {
//        if(index == arr.length) {
//            int i = 0;
//            for(; i < 4; i++) {
//                if(bucket[i] != lenSide) {
//                    break;
//                }
//            }
//            if(i == 4) {
//                flag = true;
//            }
//        }
//        for(int i = 0; i < 4; i++) {
//            if(arr[index] + bucket[i] > lenSide) {//桶装不下了
//                continue;
//            }
//            bucket[i] += arr[index];
//            dfs(arr, lenSide, bucket, index + 1)
//            bucket[i] -= arr[index];
//        }
//    }
//
//    //2.火柴拼正方形(回溯 + 双剪枝)
//    public boolean makesquare(int[] matchsticks) {
//        int len = matchsticks.length;
//        if(len < 4) { //特判:正方形有四条边
//            return false;
//        }
//        //给所有火柴求和
//        int sum = 0;
//        for(int i = 0; i < matchsticks.length; i++) {
//            sum += matchsticks[i];
//        }
//        if(sum % 4 != 0) { //特判：正方形有四条边
//            return false;
//        }
//        //求出每一条边的长度
//        int lenSide = sum / 4;
//        //剪枝：降序排序更早触发回溯中的第一个continue
//        Arrays.sort(matchsticks);
//        //降序
//        for(int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
//            int tmp = matchsticks[i];
//            matchsticks[i] = matchsticks[j];
//            matchsticks[j] = tmp;
//        }
//        //四个桶
//        int[] bucket = new int[4];
//        return dfs(matchsticks, lenSide, bucket, 0);
//    }
//
//    private boolean dfs(int[] arr, int lenSide, int[] bucket, int index) {
//        if(index == arr.length) {
//            return true;
//        }
//        for(int i = 0; i < 4; i++) {
//            if(arr[index] + bucket[i] > lenSide) {//桶装不下了
//                continue;
//            }
//            bucket[i] += arr[index];
//            if(dfs(arr, lenSide, bucket, index + 1)) {
//                return true;
//            }
//            bucket[i] -= arr[index];
//            if(bucket[i] == 0) {
//                return false;
//            }
//        }
//        return false;
//    }
//    //2.划分为k个相等的子集(回溯 + 双剪枝)
//    public boolean canPartitionKSubsets(int[] nums, int k) {
//        if(nums.length < k) {//比均分的数目还小就肯定不能均分
//            return false;
//        }
//        int sum = 0;
//        for(int i = 0; i < nums.length; i++) {
//            sum += nums[i];
//        }
//        if(sum % k != 0) {//想要均分成k个区间，那么每个区间的值一定相等，因此sum一定能被k整除
//            return false;
//        }
//        int len = sum / k;//每个区间要满足的大小
//        //桶
//        int[] bucket = new int[k];
//        //剪枝：倒序效率更高
//        Arrays.sort(nums);
//        for(int i = 0, j = nums.length - 1; i < j; i++, j--) {
//            int tmp = nums[i];
//            nums[i] = nums[j];
//            nums[j] = tmp;
//        }
//        return dfs(nums, bucket, len, k, 0);
//    }
//
//    private boolean dfs(int[] nums, int[] bucket, int len, int k, int index) {
//        if(nums.length == index) {
//            return true;
//        }
//        for(int i = 0; i < k; i++) {
//            if(bucket[i] + nums[index] > len) {//装不下，就放到下一个桶中去
//                continue;
//            }
//            bucket[i] += nums[index];
//            if(dfs(nums, bucket, len, k, index + 1)) {
//                return true;
//            }
//            bucket[i] -= nums[index];
//            if(bucket[i] == 0) return false;//到了这儿，若为0，说明没有合适的值等于len
//        }
//        return false;
//    }
//
//    //3.优美的排列(回溯)
//    private int count;
//    public int countArrangement(int n) {
//        boolean[] path = new boolean[n];
//        dfs(path, n, 0);
//        return count;
//    }
//
//    private void dfs( boolean[] path, int n, int index) {
//        if(index == n) {
//            count++;
//            return;
//        }
//        for(int i = 1; i <= n; i++) {//i表示数组内容,index + 1表示运算数组下标
//            if(path[i - 1]) {
//                continue;
//            }
//            if(i % (index + 1) != 0 && (index + 1) % i != 0) {//不优美的排列
//                continue;
//            }
//            path[i - 1] = true;
//            dfs(path, n, index + 1);
//            path[i - 1] = false;
//        }
//    }
//
//    //4.面试题 08.09. 括号(回溯)
//    private List<String> ret = new ArrayList<>();
//    private StringBuilder path = new StringBuilder();
//    public List<String> generateParenthesis(int n) {
//        char[] choose = {'(', ')'};
//        dfs(n, choose, 0);
//        return ret;
//    }
//
//    private void dfs(int n, char[] choose, int ans) {
//        if(path.length() == n * 2 && ans == 0) {
//            ret.add(new String(path));
//            return;
//        }else if(path.length() == n * 2 && ans != 0) {
//            return;
//        }
//        for(int i = 0; i < 2; i++) {
//            if(ans < 0 || ans > n) {//小于零就没救了,或者大于n
//                return;
//            }
//            path.append(choose[i]);
//            if(choose[i] == '(') {
//                ans++;
//            } else {
//                ans--;
//            }
//            dfs(n, choose, ans);
//            path.deleteCharAt(path.length() - 1);
//            if(choose[i] == '(') {
//                ans--;
//            } else {
//                ans++;
//            }
//        }
//    }
//
//    //5.面试题 08.04. 幂集(回溯)
//    private List<List<Integer>> ret = new ArrayList<>();
//    private List<Integer> path = new ArrayList<>();
//    public List<List<Integer>> subsets(int[] nums) {
//        boolean[] flag = new boolean[nums.length];
//        dfs(nums, flag, 0);
//        return ret;
//    }
//
//    private void dfs(int[] nums, boolean[] flag, int begin) {
//        ret.add(new ArrayList<>(path));
//        for(int i = begin; i < nums.length; i++) {
//            if(flag[i]) {
//                return;
//            }
//            flag[i] = true;
//            path.add(nums[i]);
//            dfs(nums, flag, begin + 1);
//            path.remove(path.size() - 1);
//            flag[i] = false;
//        }
//    }
//
//    //6.串联字符串的最大长度(回溯)
//    private int maxRet = 0;
//    public int maxLength(List<String> arr) {
//        boolean[] flag = new boolean[arr.size()];
//        Set<Character> path = new HashSet<>();
//        dfs(arr, path, flag, 0);
//        return maxRet;
//    }
//
//    private void dfs(List<String> arr, Set<Character> path,
//                     boolean[] flag, int begin) {
//        if(path.size() > maxRet) {
//            maxRet = path.size();
//        }
//        for(int i = begin; i < arr.size(); i++) {
//            if(flag[i]) {
//                continue;
//            }
//            char[] chs = arr.get(i).toCharArray();
//            boolean fg = false;
//            for(char ch : chs) {//判断一
//                if(path.contains(ch)) {
//                    fg = true;
//                    break;
//                }
//            }
//            if(fg) continue;
//            HashSet<Character> tmp = new HashSet<>();//判断二：检查自身有无重复
//            for(char ch : chs) {
//                if(tmp.contains(ch)) {
//                    fg = true;
//                    break;
//                }
//                tmp.add(ch);
//            }
//            if(fg) continue;
//            flag[i] = true;
//            for(char ch : chs) path.add(ch);
//            dfs(arr, path, flag, i + 1);
//            for(char ch : chs) path.remove(ch);
//            flag[i] = false;
//        }
//    }
//
//    //7.面试题 08.07. 无重复字符串的排列组合(回溯)
//    private List<StringBuilder> list = new ArrayList<>();
//    private StringBuilder path = new StringBuilder();
//    public String[] permutation(String S) {
//        char[] s = S.toCharArray();
//        boolean[] flag =  new boolean[s.length];
//        dfs(s, flag);
//        String[] ret = new String[list.size()];
//        for(int i = 0; i < list.size(); i++) {
//            ret[i] = list.get(i).toString();
//        }
//        return ret;
//    }
//
//    private void dfs(char[] s, boolean[] flag) {
//        if(path.length() == s.length) {
//            list.add(new StringBuilder(path));
//            return;
//        }
//        for(int i = 0; i < s.length; i++) {
//            if(flag[i]) {
//                continue;
//            }
//            path.append(s[i]);
//            flag[i] = true;
//            dfs(s, flag);
//            path.deleteCharAt(path.length() - 1);
//            flag[i] = false;
//        }
//    }
//
//    //8.统计按位或能得到最大值的子集数目(回溯 + Map)
//    private Map<Integer, Integer> map = new HashMap<>();
//    public int countMaxOrSubsets(int[] nums) {
//        //先求子集
//        boolean[] flag = new boolean[nums.length];
//        dfs(nums, flag, 0, 0, 0);
//        int maxNumCount = 0;
//        int maxNum = 0;
//        for(int key : map.keySet()) {
//            if(key > maxNum) {
//                maxNum = key;
//                maxNumCount = map.get(key);
//            }
//        }
//        return maxNumCount;
//    }
//
//    private void dfs(int[] nums, boolean[] flag, int begin, int ans, int prev) {
//        if(begin >= nums.length) {
//            return;
//        }
//
//        for(int i = begin; i < nums.length; i++) {
//            if(flag[i]) {
//                continue;
//            }
//            prev = ans;
//            ans |= nums[i];
//            flag[i] = true;
//            map.put(ans, map.getOrDefault(ans, 0) + 1);
//            dfs(nums, flag, i + 1, ans, prev);
//            flag[i] = false;
//            ans = prev;
//        }
//    }
//
//    //9.模糊坐标(真恶心)
//    public List<String> ambiguousCoordinates(String s) {
//        //把字符串用逗号分割成两个部分，然后用逗号分别去枚举两部分
//        int len = s.length();
//        //去掉括号
//        s = s.substring(1, len - 1);
//        List<String> list = new ArrayList<>();
//        //枚举小数点出现的位置
//        for(int i = 1; i < len - 2; i++) {
//            List<String> part1 = strSub(s.substring(0, i));
//            List<String> part2 = strSub(s.substring(i));
//            //拼接每一种可能
//            for(String p1 : part1) {
//                for(String p2 : part2) {
//                    list.add("(" + p1 + ", " + p2 + ")");
//                }
//            }
//        }
//        return list;
//    }
//    //寻找小数点出现的可能
//    private List<String> strSub(String s) {
//        List<String> list = new ArrayList<>();
//        //本身长度为1或者第一个数字不等于0， 那么这算是一种情况，即自身为一个整数
//        if(s.length() == 1 || s.charAt(0) != '0') {
//            list.add(s);
//        }
//        for(int i = 1; i < s.length(); i++) {
//            String s1 = s.substring(0, i);
//            String s2 = s.substring(i);
//            //只要首尾不等于0，并且末尾不为0，就可以依次用.分割
//            if((s1.length() == 1 || s.charAt(0) != '0') &&
//                    (s2.charAt(s2.length() - 1) != '0')) {
//                list.add(s1 + "." + s2);
//            }
//        }
//        return list;
//    }
    
//    //10.剑指 Offer II 079. 所有子集(最后的战役)
//    private List<List<Integer>> list = new ArrayList<>();
//    private List<Integer> path = new ArrayList<>();
//    public List<List<Integer>> subsets(int[] nums) {
//        boolean[] flag = new boolean[nums.length];
//        dfs(nums, flag, 0);
//        return list;
//    }
//
//    private void dfs(int[] nums, boolean[] flag, int begin) {
//        list.add(new ArrayList<>(path));
//        for(int i = begin; i < nums.length; i++) {
//            if(flag[i]) {
//                continue;
//            }
//            flag[i] = true;
//            path.add(nums[i]);
//            dfs(nums, flag, i + 1);
//            path.remove(path.size() - 1);
//            flag[i] = false;
//        }
//    }
//
//    //剑指 Offer II 080. 含有 k 个元素的组合(回溯二刷)
//    private List<List<Integer>> list = new ArrayList<>();
//    private List<Integer> path = new ArrayList<>();
//    public List<List<Integer>> combine(int n, int k) {
//        boolean[] flag = new boolean[n];
//        dfs(n, k, flag, 1);
//        return list;
//    }
//
//    private void dfs(int n, int k, boolean[] flag, int begin) {
//        if(path.size() == k) {
//            list.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = begin; i <= n; i++) {
//            if(flag[i - 1]) {
//                continue;
//            }
//            flag[i - 1] = true;
//            path.add(i);
//            dfs(n, k, flag, i + 1);
//            path.remove(path.size() - 1);
//            flag[i - 1] = false;
//        }
//    }

    //剑指 Offer II 081. 允许重复选择元素的组合(回溯二刷)
    private List<List<Integer>> list = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, 0);
        return list;
    }
    private void dfs(int[] candidates, int target, int begin) {
        if(target == 0) {
            list.add(new ArrayList<>(path));
            return;
        } else if(target < 0) {
            return;
        }
        for(int i = begin; i < candidates.length; i++) {
            path.add(candidates[i]);
            dfs(candidates, target - candidates[i], i);
            path.remove(path.size() - 1);
        }
    }
}

class Main {
    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 5};
        StringBuilder str = new StringBuilder();
        Solution solution = new Solution();
    }
}
